package tree;

import pojo.TreeNode;

/**
 * 功能描述: 一颗树中的两个结点之间的最大的距离
 * 2024/05/19
 * <p>
 * ZhangYi
 */
public class MaxDistinceBetweenNodeUtils {
    /***
     * 确认要返回的节点信息
     */
    public static class Info{
        private int maxDistance;
        private int height;

        public Info(int maxDistance,
                    int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }


    public static int getMaxDistance(TreeNode root){
        if (root == null){
            return 0;
        }
        return getMaxDistanceHelper(root).maxDistance;
    }

    private static Info getMaxDistanceHelper(TreeNode root) {

        if (root == null ){
            return new Info(0,0);
        }
        Info leftInfo = getMaxDistanceHelper(root.left);
        Info rightInfo = getMaxDistanceHelper(root.right);
        int height=Math.max(leftInfo.height,rightInfo.height)+1;
        int maxDistance=Math.max(Math.max(leftInfo.maxDistance,rightInfo.maxDistance),
                                 leftInfo.height+rightInfo.height+1);

        return new Info(maxDistance,height);
    }

    public static void main(String[] args){
        TreeNode root = generateFullTree();
        TreeNode leftRoot = generateLeftTree();
        TreeNode rightRoot = generateRightTree();

        System.out.println(getMaxDistance(root));
        System.out.println(getMaxDistance(leftRoot));
        System.out.println(getMaxDistance(rightRoot));
    }

    private static TreeNode generateRightTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.right= new TreeNode(11,
                                     "4");

        treeNode.right.left = new TreeNode(11,
                                          "4");
        treeNode.right.right = new TreeNode(11,
                                           "4");
        treeNode.right.left.left = new TreeNode(11,
                                               "4");
        treeNode.right.left.right = new TreeNode(11,
                                                "4");
        treeNode.right.right.left = new TreeNode(11,
                                                "4");
        treeNode.right.right.right = new TreeNode(11,
                                                 "4");


        return treeNode;
    }

    private static TreeNode generateLeftTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.right= new TreeNode(11,
                                          "4");

        treeNode.left.left = new TreeNode(11,
                                          "4");
        treeNode.left.right = new TreeNode(11,
                                          "4");
        treeNode.left.left.left = new TreeNode(11,
                                          "4");
        treeNode.left.left.right = new TreeNode(11,
                                          "4");
        treeNode.left.right.left = new TreeNode(11,
                                          "4");
        treeNode.left.right.right = new TreeNode(11,
                                          "4");


        return treeNode;
    }

    private static TreeNode generateFullTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.left.left = new TreeNode(11,
                                          "4");


        treeNode.right = new TreeNode(34,
                                      "3");
        treeNode.right.left = new TreeNode(33,
                                           "6");
        treeNode.right.right = new TreeNode(35,
                                            "7");
        treeNode.right.right.right = new TreeNode(36,
                                                  "8");
        return treeNode;
    }
}
